/**
 * 494. 目标和
 * https://leetcode.cn/problems/target-sum/description/
 */
class Solution {
    int path;
    int count;
    int target;
    public int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums, 0, 0);
        return count;
    }

    //参数传进dfs中的版本
    void dfs(int[] nums, int pos, int _path) {
        if(pos == nums.length) {
            if(_path == target) count++;
            return;
        }
        //加法
        dfs(nums, pos + 1, _path + nums[pos]);
        //减法
        dfs(nums, pos + 1, _path - nums[pos]);
    }

    //全局变量版本
    void dfs1(int[] nums, int pos) {
        if(pos == nums.length) {
            if(path == target) count++;
            return;
        }
        //加法
        path += nums[pos];
        dfs1(nums, pos + 1);
        path -= nums[pos];//回溯
        //减法
        path -= nums[pos];
        dfs1(nums, pos + 1);
        path += nums[pos];
    }
}